//
// Description: 1143. 最长公共子序列
// Created by Loading on 2021/4/3.
//

#include <bits/stdc++.h>

using namespace std;

//动态规划
int longestCommonSubsequence(string text1, string text2) {
    constexpr int N = 1e3 + 10;
    int dp[N][N];
    //初始化动态规划数组
    for (auto &i : dp) {
        memset(i, 0, N);
    }

//    //考虑动态规划边界情况，在这里，下标与dp数组下标一致。需要增加i与j是否为0的判断。
/* 可以将dp数组错开一位 */
//    for (int i = 0; i < text1.size(); ++i) {
//        for (int j = 0; j < text2.size(); ++j) {
//            if (text1[i] == text2[j]) {//可以匹配
//                if (i == 0 || j == 0) {
//                    dp[i][j] = 1;
//                } else {
//                    //更新dp数组，为上一个字符的值+1
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }
//            } else {//未能匹配
//                if (i == 0 && j == 0) {
//                    dp[i][j] = 0;
//                } else if (i == 0) {
//                    dp[i][j] = dp[i][j - 1];
//                } else if (j == 0) {
//                    dp[i][j] = dp[i - 1][j];
//                } else {
//                    //要获取最长公共子序列，取两者最大值
//                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//                }
//            }
//        }
//    }
//
//    return dp[text1.size() - 1][text2.size() - 1];


    //将dp数组错开一位实现
    for (int i = 1; i <= text1.size(); ++i) {
        for (int j = 1; j <= text2.size(); ++j) {
            if (text1[i - 1] == text2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[text1.size()][text2.size()];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";
    cout << longestCommonSubsequence(text1, text2) << endl;
}